package sword;

import java.util.LinkedList;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/22 20:01
 * https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
 */
public class Title59I {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return new int[]{};
        }
        int[] result = new int[n - k + 1];
        int count = 0;
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            //[i-k+1, i]
            if (!list.isEmpty() && list.peek() < i - k + 1) {
                list.poll();
            }
            //维持单调队列
            while (!list.isEmpty() && nums[i] > nums[list.getLast()]) {
                list.pollLast();
            }
            list.offer(i);
            if (i >= k - 1) {
                result[count++] = nums[list.peek()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        maxSlidingWindow(new int[]{}, 0);
    }
}
